from functools import lru_cache


class Solution:
    def restoreIpAddresses(self, s: str):

        @lru_cache(None)
        def getNode(start, lastNum):
            r2 = []
            if len(s) <= start:
                return r2
            if lastNum == 0:
                return r2
            if lastNum == 1:
                tmp = s[start:]
                if not (len(tmp) > 1 and tmp[0] == '0') and 0 <= int(tmp) <= 255:
                    r2.append(tmp)
            else:
                tmp = ""
                for i in range(start, len(s)):
                    tmp += s[i]
                    if len(tmp)>1 and tmp[0]=='0':
                        break
                    if 0 <= int(tmp) <= 255:
                        r3 = getNode(i + 1, lastNum - 1)
                        for j in r3:
                            r2.append(tmp+"."+j)
                    else:
                        break

            return r2

        return getNode(0,4)


if __name__ == '__main__':
    so = Solution()
    n = "010010"
    r = so.restoreIpAddresses(n)
    print(r)
